//https://leetcode.cn/problems/reverse-linked-list/
package codeRandomThoughts.Test206反转链表;

import codeRandomThoughts.utils.ListNode;

//二刷
public class Solution2 {

    public ListNode reverseList2(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        ListNode next = new ListNode();
        while (curr != null) {
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        //此时curr为null
        return pre;
    }

    //尝试写一个递归版本
    public ListNode reverseList(ListNode head) {
        //递归的终止条件
        if (head == null) return null;//没有节点
        if (head.next == null) return head;//只有一个节点 必须写 不然访问head.next.next可能会报错

        //递归返回的就是反转后链表的头节点
        ListNode headAfterReverse = reverseList(head.next);
        head.next.next = head;
        head.next = null;//这一句很重要,不然会变成环形链表
        return headAfterReverse;
    }
}
